package com.yq.woshouCode;

import java.util.Arrays;

/**
 * @ClassName TopN
 * @Description 手写topN 大顶堆实现
 * @Author yaoqiang
 * @Date 2021/2/5 16:55
 * @Version 1.0
 */
public class TopN {
    public static void main(String[] args) {
        int[] arr={4,6,8,5,9};
        int n=3;//top第n=3个
        sortHeap(arr);
        System.out.println(Arrays.toString(arr));


        //生成随机的1亿个数
        int arr1[]=new int[80000];
        for (int i=0;i< 79999;i++){
            arr1[i]=(int)(Math.random()*80000);
        }
        sortHeap(arr1);

        int[] newArr=new int[n];
        for(int j=0;j<n;j++){
            int index=arr1.length-j-1;
            newArr[j] =arr1[index];
        }
        System.out.println(Arrays.toString(newArr));

    }

    private static void sortHeap(int[] arr) {
        for (int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }

        int temp=0;

        for (int k=arr.length-1 ;k>0;k--){
            temp=arr[k];
            arr[k]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,k);
        }


    }

    private static void adjustHeap(int[] arr, int i, int length) {
        int temp=arr[i];
        for (int k=2*i+1;k<length;k=k*2+1){
            if (k+1<length && arr[k]<arr[k+1])
            {k++;}
            if (arr[i]<arr[k]){
                arr[i]=arr[k];
                i=k;
            }else {break;}
        }
        arr[i]=temp;
//        System.out.println(Arrays.toString(arr));
    }

}
